package edu.dhu.leetcode.solution13;

import java.util.LinkedList;

/**
 * @Author ：snow
 * @Date ：Created in 2020-08-02
 * @Description：
 * @Modified By：
 * @Version:
 */
public class Solution {
    private boolean[][] marked ;
    private int m,n,k;
    public int movingCount(int m, int n, int k) {
        marked = new boolean[m][n];
        this.m = m;
        this.n = n;
        this.k = k;
        return dfs(0, 0);

    }

    /**
     *深度优先搜素，向右向下搜索
     * @param i 行
     * @param j 列
     * @return
     */
    private int dfs(int i, int j){
        if (i >= m || j >= n || (bitSum(i) + bitSum(j)) > k || marked[i][j]) return 0;
        marked[i][j] = true;
        return 1 + dfs(i + 1, j) + dfs(i, j + 1); // 当前节点加上向右和向下的搜索结果和
    }

    /**
     * 广度优先搜索
     * @param m
     * @param m
     * @param k
     * @return
     */
    public  int bfsMovingCount(int m, int n, int k){
        boolean [][] visited = new boolean[m][n];
        LinkedList<int[]> queue = new LinkedList<>();
        queue.add(new int [] {0, 0});
        int count = 0;
        while (queue.size() > 0){
            int[] x = queue.poll();
            int i = x[0]; // 行
            int j = x[1];
            if (i >= m || j >= n || (bitSum(i) + bitSum(j)) > k) continue;
            visited[i][j] = true;
            count ++;
            queue.add(new int[]{i + 1, j});
            queue.add(new int[]{i, j + 1 });
        }
        return count;
    }

    /**
     * 计算位数和
     * @param n
     * @return
     */
   private int bitSum(int n){
        int sum = 0;
        while (n > 0){
            sum += n % 10; // 个位
            n /= 10; // 删除个位
        }
        return sum;
   }

    public static void main(String[] args) {
        Solution s = new Solution();
        int ret = s.bfsMovingCount(2, 3, 1);
        System.out.println(ret);
    }
}
